package algorithm.problems.hashing;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by gouthamvidyapradhan on 25/02/2017.
 * Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
 * <p>
 * Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
 * <p>
 * The order of output does not matter.
 * <p>
 * Example 1:
 * <p>
 * Input:
 * s: "cbaebabacd" p: "abc"
 * <p>
 * Output:
 * [0, 6]
 * <p>
 * Explanation:
 * The substring with start index = 0 is "cba", which is an anagram of "abc".
 * The substring with start index = 6 is "bac", which is an anagram of "abc".
 * Example 2:
 * <p>
 * Input:
 * s: "abab" p: "ab"
 * <p>
 * Output:
 * [0, 1, 2]
 * <p>
 * Explanation:
 * The substring with start index = 0 is "ab", which is an anagram of "ab".
 * The substring with start index = 1 is "ba", which is an anagram of "ab".
 * The substring with start index = 2 is "ab", which is an anagram of "ab".
 */
public class Anagrams {
    int[] TC = new int[256];
    int[] PC = new int[256];

    /**
     * Main method
     *
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        List<Integer> result = new Anagrams().findAnagrams("abab", "ab");
        result.forEach(System.out::print);
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int pLen = p.length();
        if (pLen > s.length()) return result;
        Arrays.fill(TC, 0);
        Arrays.fill(PC, 0);
        for (int i = 0; i < pLen; i++) {
            TC[s.charAt(i)]++;
            PC[p.charAt(i)]++;
        }

        int i = pLen;
        for (int l = s.length(); i < l; i++) {
            if (compare())
                result.add(i - pLen);

            TC[s.charAt(i)]++;
            TC[s.charAt(i - pLen)]--;
        }
        if (compare())
            result.add(i - pLen);

        return result;
    }

    private boolean compare() {
        for (int i = 0; i < 256; i++) {
            if (TC[i] != PC[i])
                return false;
        }
        return true;
    }

}
